\documentclass{llncs}
%
\usepackage{makeidx}  % allows for indexgeneration
%
\usepackage{graphicx}
\usepackage{stfloats}
\usepackage{amsmath}
\usepackage{bbm}
\usepackage{amssymb}
\usepackage{multirow}
\usepackage{mathrsfs}
\usepackage{url}
\usepackage{listings}
\usepackage{color}
\usepackage{wrapfig}
\usepackage{mathtools}
 
\usepackage{algorithm}
\usepackage{algorithmic}


\lstloadlanguages{XML}


\newcommand{\beq}{\begin{equation}}
\newcommand{\enq}{\end{equation}}
\newcounter{mytempeqncnt}
\newcommand{\bquote}{\begin{quote}}
\newcommand{\equote}{\end{quote}}

\newcommand{\todo}[1]{\textcolor{red}{@TODO: #1}}
\newcommand{\dtr}[1]{\textbf{\textit{#1}$^\textbf{[dtr]}$}}
\algsetup{linenosize=\small}
\begin{document}
\frontmatter          % for the preliminaries
%
\pagestyle{headings}  % switches on printing of running heads
% \addtocmark{Prior information and event spaces} % additional mark in the TOC

\title{Effective and Efficient Candidate Selection over Multiple Heterogeneous Datasets}

%
\titlerunning{}  % abbreviated title (for running head)
%                                     also used for the TOC unless
%                                     \toctitle is used
\author{Samur Araujo\inst{1}, Duc Thanh Tran\inst{2}, Arjen de Vries\inst{1}, Marcel Reinders\inst{1}}

% Jeffrey Dean \and David Grove \and Craig Chambers \and Kim~B.~Bruce \and
% Elsa Bertino}
% %
\authorrunning{}   % abbreviated author list (for running head)
 

\institute{Delft University of Technology, PO Box 5031, 2600 GA Delft, the Netherlands \email{{S.F.CardosodeAraujo}}
\and Karlsruher Institute of Technology, Germany \\
\email{ducthanh.tran@kit.edu}}

\maketitle
\begin{abstract} 
To build high quality interlinking (owl:sameas) between different datasets is a challenge for the Linked Data. Current approaches tackle the problem of scalability in this process, focusing on finding candidate matches using a relatively simple but quick matching technique, which in a second phase are refined using a more expensive technique. In this paper, we tackle the effective and efficiency of the problem of \emph{candidate selection} over multiple heterogeneous datasets. We pose it as the problem of finding a query that retrieves a subset A of target instances that are possible matches for a source instance. We propose Sonda, a \emph{branch-and-bound based optimization framework} that can build candidate queries and evaluate the minimal set of queries that produces less candidates. We intensively evaluate our approach on fourteen RDF datasets provide by two benchmarks. Our results shows that our framework achieve the best F1, towards Reduction Ratio (RR) and Pair Completeness (PC), in 96\% of the cases. 
 
\textbf{Keywords}: data integration, RDF interlinking, instance matching, candidate selection, query optimization.
\end{abstract} 

\input{sec-intro}
  
\input{sec-problem}
\input{sec-keyselection}
\input{sec-approach}
 
\input{sec-experiment}
\input{sec-related}

\section{Conclusions}

In this paper, we investigated the problem of candidate selection in the large and heterogeneous environment of the Web.  We pose it as the problem of finding a query that retrieves a subset A of target instances that are possible matches for a source instance. We propose Sonda, a \emph{branch-and-bound based optimization framework} that can build such a candidate queries and evaluate the minimal set of those queries to build candidates sets. Our algorithm are able to find key among multiples dataset, aligned them, and build queries that are used to select candidates. Then, those queries are used in our search framework, that efficiently and effectively select the query that minimize the cardinality of a candidate set. We intensively evaluate our approach on fourteen RDF datasets provide by two benchmarks. Our results show that our framework achieve the best F1, towards Reduction Ratio (RR) and Pair Completeness (PC), except for one case. We implemented Sonda and make it available as an unsupervised tool for interlinking two RDF datasets accessible via SPARQL endpoints.


\bibliographystyle{abbrv}
\bibliography{iswc}
\end{document}
